package com.peng.leetcode.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * FindSmallestSetOfVertices
 *
 * 给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点  fromi 到点 toi 的有向边。
 *
 * 找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。
 *
 * 你可以以任意顺序返回这些节点编号。
 *
 * 链接：https://leetcode-cn.com/problems/minimum-number-of-vertices-to-reach-all-nodes
 *
 * @author: lupeng6
 * @create: 2021/1/29 20:28
 */
public class FindSmallestSetOfVertices {

    public static void main(String[] args) {

    }

    private int[] inDegree;

    private List<List<Integer>> adjacency;

    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        this.inDegree = new int[n];
        this.adjacency = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjacency.add(new ArrayList<>());
        }

        for (List<Integer> edge : edges) {
            Integer start = edge.get(0);
            Integer target = edge.get(1);
            // init 邻居
            adjacency.get(start).add(target);

            // init 入度
            inDegree[target]++;
        }

        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < inDegree.length; i++) {
            int start = inDegree[i];
            if (start == 0) {
                result.add(i);
            }
        }

        return result;
    }

}
